解答1[Java]:
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set1 = new HashSet();
HashSet<Integer> set2 = new HashSet();
HashSet resultSet = new HashSet();
int[] result = new int[nums1.length];
int resultIndex = 0;
for(int num: nums1){
set1.add(num);
}
for(int num:nums2){
set2.add(num);
}
for (Integer num :set2){
if(set1.contains(num)){
result[resultIndex++] = num;
}
}
return Arrays.copyOf(result, resultIndex);
}
}
复杂度分析
没错,hashSet的contains方法是调用map.containsKey(O)方法的,containsKey(o)是根据hash函数去做散列的,所以与元素的多少无关,无论是多少元素containsKey(o)的时间复杂度基本上O(1)。
解答2[Java]:
import java.util.Arrays;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int num : nums1) {
min = Math.min(min, num);
max = Math.max(max, num);
}
boolean[] exist = new boolean[max - min + 1];
for (int num : nums1) exist[num - min] = true;
int[] result = new int[nums2.length];
int index = 0;
for (int num : nums2) {
if (num <= max && num >= min && exist[num - min]) {
result[index++] = num;
exist[num - min] = false; //remove from exist array to avoid duplicate
}
}
return Arrays.copyOf(result, index);
}
}
思路
很巧妙的一个算法,先把一个数组的最大值和最小值圈起来。
复杂度分析
空间复杂度:
result 数组和 exist 数组为 或者 。m 和 h 是两个数组的长度。
时间复杂度:。